import random
import matplotlib.pyplot as plt
def generate_random_board():
    board = [random.randint(0, 7) for _ in range(8)]
    return board
def calculate_attack_pairs(board:list):
    pairs = 0
    for i in range(len(board)):
        for j in range(i + 1, len(board)):
            if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
                pairs += 1
    return pairs
def greedy_hill_climbing(board):
    """
    贪婪爬山法
    :param board:
    :return:返回步数和棋盘
    """
    steps = 0
    while True:
        attack_pairs = calculate_attack_pairs(board)
        if attack_pairs == 0:
            return board, steps
        best_board = list(board)
        current_board=list(board)
        min_pairs = attack_pairs
        for col in range(len(board)):
            for row in range(len(board)):
                if board[col] == row:
                    continue
                board[col] = row
                new_pairs = calculate_attack_pairs(board)
                if new_pairs < min_pairs:
                    min_pairs = new_pairs
                    best_board = list(board)
                else:
                    board=list(current_board)
        board = list(best_board)
        steps += 1
        if min_pairs == attack_pairs:
            return board, steps

def sideways_hill_climbing(board):
    """侧向移动"""
    steps = 0
    max_sideways_moves = 100  # 设置最大侧向移动次数
    while True:
        attack_pairs = calculate_attack_pairs(board)
        if attack_pairs == 0:
            return board, steps
        best_board = list(board)
        min_pairs = attack_pairs
        next_boards = []

        for col in range(len(board)):
            for row in range(len(board)):
                if board[col] == row:
                    continue
                new_board = list(board)
                new_board[col] = row
                new_pairs = calculate_attack_pairs(new_board)
                if new_pairs < min_pairs:
                    min_pairs = new_pairs
                    best_board = list(new_board)
                elif new_pairs == min_pairs:
                    next_boards.append(new_board)

        if min_pairs == attack_pairs:
            if len(next_boards) > 0 and steps < max_sideways_moves:
                board = random.choice(next_boards)
            else:
                return board, steps
        else:
            board = best_board
        steps += 1


def renew_hill_climbing(board):
    steps = 0
    while True:
        attack_pairs = calculate_attack_pairs(board)
        if attack_pairs == 0:
            return board, steps
        best_board = list(board)
        current_board = list(board)
        min_pairs = attack_pairs
        for col in range(len(board)):
            for row in range(len(board)):
                if board[col] == row:
                    continue
                board[col] = row
                new_pairs = calculate_attack_pairs(board)
                if new_pairs < min_pairs:
                    min_pairs = new_pairs
                    best_board = list(board)
                else:
                    board = list(current_board)
        board = list(best_board)
        steps += 1
        if min_pairs == attack_pairs:
            board=generate_random_board()


successful_solutions = 0
total_steps = 0
convergence_curve = []
count=0

for _ in range(1000):
    board = generate_random_board()
    # result, steps = renew_hill_climbing(board)
    result, steps = sideways_hill_climbing(board)
    # result, steps = greedy_hill_climbing(board)
    if calculate_attack_pairs(result) == 0:
        successful_solutions += 1
        total_steps += steps
        convergence_curve.append(total_steps/successful_solutions)
average_steps = total_steps / successful_solutions
print("Successful solutions:", successful_solutions)
print("Average steps:", average_steps)

plt.plot(convergence_curve)
plt.xlabel("Number of Runs")
plt.ylabel("Average Steps to Optimal Solution")
plt.title("Convergence Curve")
plt.show()